package com.kingwood.algorithm.test;

import java.io.*;
import java.util.Scanner;

/**
 * @Author 22025812
 * @Description: 高级排序
 * @Date: 2024/3/1 14:02
 * @Modified By：
 * @Version 1.0
 */
public class HighLevelSort {

    public static int MAXN = 1000;
    public static int[] arr = new int[MAXN];
    public static int[] help = new int[MAXN];
    public static int n = MAXN;

    /**
     * 归并排序，递归版
     * @param l
     * @param r
     */
    public static void mergeSort1(int l, int r) {
        if (l == r) {
            return;
        }

        int m = (l + r) / 2;
        mergeSort1(l, m);
        mergeSort1(m + 1, r);
        merge(l, m, r);
    }

    public static void merge(int l, int m, int r) {
        int i = l;
        int a = l;
        int b = m + 1;

        while (a <= m && b <= r) {
            help[i++] = arr[a] < arr[b] ? arr[a++] : arr[b++];
        }

        while (a <= m) {
            help[i++] = arr[a++];
        }
        while (b <= r) {
            help[i++] = arr[b++];
        }

        for (int j = l; j <= r; j++) {
            arr[j] = help[j];
        }
    }

    /**
     * 归并排序，非递归版，通过步长实现
     */
    public static void mergeSort2() {
        for (int l, m, r, step = 1; step < n; step <<= 1) {
            l = 0;
            while (l < n) {
                m = l + step - 1;
                if (m + 1 >= n) {
                    break;
                }

                r = Math.min(l + (step << 1) - 1, n - 1);
                merge(l, m, r);
                l = r + 1;
            }
        }
    }

    public static void main(String[] args) throws IOException {
//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//        StreamTokenizer in = new StreamTokenizer(br);
//        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
//
//        while (in.nextToken() != StreamTokenizer.TT_EOF) {
//            n = (int) in.nval;
//            for (int i = 0; i < n; i++) {
//                in.nextToken();
//                arr[i] = (int) in.nval;
//            }
//
//            mergeSort1(0, n - 1);
//            // mergeSort2();
//
//            out.print(arr[0]);
//            for (int i=1; i<n; i++) {
//                out.print(" " + arr[i]);
//            }
//            out.println();
//        }

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }

        mergeSort1(0, n - 1);
        // mergeSort2();

        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}
